1629 곱셈

나머지 지수승 관련한 이산수학 교재 캡처 추가. 이 알고리즘이 기반한 원리는 b4modm 이나 (b2modm)(b2modm)modm 이나 같다는 것이다. 주목할 변수는 x일지 몰라도 그 x에 붙일 계수를 알기 위해선 당연하게도 power를 지수승만큼 증가시켜야 한다. 그런데 그냥 b1 b2 b3 ... 이런식이 아닌, b21 b22 b23 이런 식으로 증가하기 때문에 power를 매 이터레이션마다 제곱을 시키는 것이다.

아래 교재의 예시인 3644mod645를 예로 들면, 644=22+27+29 이므로, 3644mod645=322327329mod645와 같다. 그래서 x는 i 가 2, 7, 9일때 x = (x * power) mod m을 구하고, power는 매 이터레이션마다 32i 를 구하고 있는거고.

software - 0.jpg

source code

"""modular exponentiation 참고: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation"""
from math import ceil, log2


def modular_exponentiation(b: int, exp: int, m: int):
    """나머지 지수승 연산을 수행하는 알고리즘.
    $
    b^{exp} \mod m
    $
    """
    x = 1
    power = b % m
    k = ceil(log2(exp)) + 1 # e의 이진전개의 길이, 1을 더하는 이유는 예외처리 때문이다. 2의 지수승을 e에 넣어보고 풀면 결과가 이상하다. 왜냐하면 아래 for문의 if문을 하나도 통과하지 않기 때문이지.

    for i in range(k):
        if (exp >> i) & 1 == 1:
            # a_i = 1 then,
            x = (x * power) % m
        power = (power * power) % m
    return x


b, exp, m = [int(x) for x in input().split()]

print(modular_exponentiation(b, exp, m))